package kyssion.leetcode.num1_50;

import kyssion.leetcode.util.ShowUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
 * <p>
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 * <p>
 * 示例:
 * <p>
 * 输入："23"
 * 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
 * 说明:
 * 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
 */
public class code17_电话号码的数字组合 {

    public static void main(String[] args) {
        ShowUtil.showList(new code17_电话号码的数字组合().letterCombinations("101010101010100213"),false);
    }

    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) {
            return new ArrayList<>();
        }
        char[][] maps = new char[][]{
                {},
                {},
                {'a', 'b', 'c'},
                {'d', 'e', 'f'},
                {'g', 'h', 'i'},
                {'j', 'k', 'l'},
                {'m', 'n', 'o'},
                {'p', 'q', 'r', 's'},
                {'t', 'u', 'v'},
                {'w', 'x', 'y', 'z'}
        };

        List<String> list = new ArrayList<>();
        char[] items = digits.toCharArray();
        int index = 0;
        char[] all = new char[items.length];
        int allIndex = 0;
        return findAll(list, items, index, all, allIndex, maps);
    }

    public List<String> findAll(List<String> list, char[] items, int index, char[] all, int allIndex, char[][] maps) {
        if (index == items.length) {
            list.add(new String(all, 0, allIndex));
            return list;
        }
        if (items[index] == '0' || items[index] == '1') {
            return findAll(list, items, index + 1, all, allIndex, maps);
        }
        char[] nowList = maps[items[index] - '0'];
        for (int a = 0; a < nowList.length; a++) {
            all[allIndex] = nowList[a];
            findAll(list, items, index + 1, all, allIndex + 1, maps);
        }
        return list;
    }
}
